package com.pan.util;

import java.util.Arrays;

/**
 * @author by panstark
 * @description
 * @notice
 * @date 2020/12/24
 */
public class BinerySearch {

    public static void sort(int[] arr){

        int length = arr.length;
        //[0....length-1]
        for (int i = 0; i < length; i++) {
            int temp = arr[i];
            int j=i;
            for(;j>0;j--){
                if(arr[j-1]>temp){
                    arr[j]=arr[j-1];
                }else{
                    break;
                }
            }
            arr[j] = temp;
        }
    }


    /**
     * 二分排序
     * @param arr
     */
    public static void binerySort(int[] arr){

        int length = arr.length;
        //[0...lenght-1]
        for (int i = 0; i < length; i++) {
            int left = 0;
            int right = i-1;
            int temp = arr[i];

            while(left<=right){
                int middle = (left+right)/2;
                if(temp>arr[middle]){
                    left=middle+1;
                }else if(temp==arr[middle]){
                    left=middle;
                    break;
                }else if (temp<arr[middle]){
                    right=middle-1;
                }
            }

            for(int j=i;j>left&&i>0;j--){
                arr[j]=arr[j-1];
            }
            arr[left]=temp;
        }

    }



    public static void main(String[] args) {
        int[] arr={6,4,7,9,3,5,6,2};
        //sort(arr);
        binerySort(arr);
        System.out.println(Arrays.toString(arr));
    }

}
